package io.lvdaxian.leetcode.dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// https://leetcode.cn/problems/pascals-triangle/

/**
 * 118. 杨辉三角
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * <p>
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] / 5
 */
public class L118_Generate_Case001 {
  public List<List<Integer>> generate(int numRows) {
    Integer[][] ans = new Integer[numRows][];
    
    // 填充数据
    for (int idx = 0; idx < numRows; idx += 1) {
      ans[idx] = new Integer[idx + 1];
      Arrays.fill(ans[idx], 1);
    }
    
    for (int i = 2; i < numRows; i += 1) {
      Integer[] prev = ans[i - 1];
      Integer[] curr = ans[i];
      for (int j = 1; j < i; j += 1) {
        curr[j] = prev[j] + prev[j - 1];
      }
    }
    
    List<List<Integer>> list = new ArrayList<>();
    for (Integer[] an : ans) {
      list.add(Arrays.asList(an));
    }
    
    return list;
  }
  
  public static void main(String[] args) {
    L118_Generate_Case001 l118GenerateCase001 = new L118_Generate_Case001();
    l118GenerateCase001.generate(5);
  }
}
